class Solution:
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        area = 0
        stack = []
        i = 0
        while i < len(heights):
            if not stack or heights[stack[-1]] < heights[i]:  # 递减
                stack.append(i)
                i += 1
            else:
                start = stack.pop()
                width = i if not stack else i-stack[-1]-1
                area = max(area, heights[start]*width)
        while stack:
            start = stack.pop()
            width = len(heights) if not stack else len(heights)-stack[-1]-1
            area = max(area, heights[start]*width)
        return area


test = Solution()
print(test.largestRectangleArea([2, 1, 5, 6, 2, 3]))
